package JZ_offer.bin_tree;

public class JZ36_Convert{
    TreeNode prev;
    TreeNode head;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        //左
        Convert(pRootOfTree.left);
        //根节点
        if(prev!=null){
            prev.right=pRootOfTree;
            pRootOfTree.left=prev;
            //prev更新到新的根节点
            prev=pRootOfTree;
        }else{
            //prev为null,说明此时的根节点就是头节点
            head=pRootOfTree;
            prev=head;
        }
        Convert(pRootOfTree.right);
        return head;
    }
//    public TreeNode Convert(TreeNode pRootOfTree) {
//        if(pRootOfTree==null){
//            return null;
//        }
//        //遍历左子树
//        TreeNode leftHead=Convert(pRootOfTree.left);
//        TreeNode leftTail=leftHead;
//        while(leftTail!=null&&leftTail.right!=null){
//            leftTail=leftTail.right;
//        }
//        if(leftTail!=null){
//            leftTail.right=pRootOfTree;
//            pRootOfTree.left=leftTail;
//        }
//        //右边
//        TreeNode rightHead=Convert(pRootOfTree.right);
//        if(rightHead!=null){
//            rightHead.left=pRootOfTree;
//            pRootOfTree.right=rightHead;
//        }
//        return leftHead==null?pRootOfTree:leftHead;
//    }
}
